package cn.algorithms_4ed.chapter5;

/**
 * #请替换掉这里的东东#
 * <p/>
 * User: root
 * Date: 13-7-24
 * Time: 上午9:39
 */
public class StringSorts {

    private static class DS {
        String name;
        int key;

        public DS(String name, int key) {
            this.name = name;
            this.key = key;
        }
    }

    private static DS[] data = new DS[20];
    private static int index = 0;
    private static int R = 6;

    static {
        addData(2, "Anderson");
        addData(3, "Brown");
        addData(3, "Davis");
        addData(4, "Garcia");
        addData(1, "Harris");
        addData(3, "Jackson");
        addData(4, "Johnson");
        addData(3, "Jones");
        addData(1, "Martin");
        addData(2, "Martinez");
        addData(2, "Miller");
        addData(1, "Moore");
        addData(2, "Robinson");
        addData(4, "Smith");
        addData(3, "Taylor");
        addData(4, "Thomas");
        addData(4, "Thompson");
        addData(2, "White");
        addData(3, "Williams");
        addData(4, "Wilson");
    }

    private static void keyIndex() {
        int N = data.length;
        String[] aux = new String[N];
        int[] count = new int[R + 1];

        for (int i = 0; i < N; i++) {
            count[data[i].key + 1]++;
        }

        for (int r = 0; r < R; r++) {
            count[r + 1] += count[r];
        }

        for (int i = 0; i < N; i++) {
            aux[count[data[i].key]++] = data[i].name;
        }

        for (int i = 0; i < N; i++) {
            data[i].name = aux[i];
        }
    }

    private static void addData(int section, String name) {
        data[index++] = new DS(name, section);
    }

    public static void main(String[] args) {
        keyIndex();
        for (DS ds : data) {
            System.out.printf("name:%10s, key:%1d\n", ds.name, ds.key);
        }
    }
}
